package com.practice.niuke.new_direct_practice.class03;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 如果给你一个二维数组， 每一个值表示这一块地形的高度， 求整块地形能装下多少水。
 */
public class Code06_TrappingRainWaterII {

	public static class Node {
		// 值
		public int value;
		// 行号
		public int row;
		// 列号
		public int col;

		public Node(int v, int r, int c) {
			value = v;
			row = r;
			col = c;
		}

	}

	/**
	 * 小根堆比较器
	 */
	public static class NodeComparator implements Comparator<Node> {

		@Override
		public int compare(Node o1, Node o2) {
			return o1.value - o2.value;
		}

	}

	/**
	 * 计算水量
	 *
	 * @param heightMap 二维数组
	 * @return int
	 */
	public static int trapRainWater(int[][] heightMap) {
		// 清理无效数据
		if (heightMap == null || heightMap.length == 0 || heightMap[0] == null || heightMap[0].length == 0) {
			return 0;
		}
		// 行数
		int N = heightMap.length;
		// 列数
		int M = heightMap[0].length;
		// 和原矩阵等规模用来记录原矩阵中的某一个位置是否进过堆，
		// isEnter[i][j] == true，说明heightMap[i][j]进过堆。
		boolean[][] isEnter = new boolean[N][M];
		// 小根堆
		PriorityQueue<Node> heap = new PriorityQueue<>(new NodeComparator());
		// 第0行进小根堆
		for (int col = 0; col < M - 1; col++) {
			isEnter[0][col] = true;
			heap.add(new Node(heightMap[0][col], 0, col));
		}
		// 第M-1列进小根堆
		for (int row = 0; row < N - 1; row++) {
			isEnter[row][M - 1] = true;
			heap.add(new Node(heightMap[row][M - 1], row, M - 1));
		}
		// 第N-1行进小根堆
		for (int col = M - 1; col > 0; col--) {
			isEnter[N - 1][col] = true;
			heap.add(new Node(heightMap[N - 1][col], N - 1, col));
		}
		// 第0列进小根堆
		for (int row = N - 1; row > 0; row--) {
			isEnter[row][0] = true;
			heap.add(new Node(heightMap[row][0], row, 0));
		}
		// 每个位置的水量累加到water上去
		int water = 0;
		// 每一个node在弹出的时候，如果value更大，更新max，否则max的值维持不变
		int max = 0;
		// 堆不为空时
		while (!heap.isEmpty()) {
			// 弹出一个节点
			Node cur = heap.poll();
			// 判断是否需要更新max
			max = Math.max(max, cur.value);
			// 当前节点的行和列
			int r = cur.row;
			int c = cur.col;
			int value = 0;
			// 如果有上面的位置并且上面的位置没有进过堆
			// 将当前节点上方的没有进过堆的节点入堆，并且在入堆时结算水量
			if (r > 0 && !isEnter[r - 1][c]) {
				value = heightMap[r - 1][c];
				// 结算水量，如果当前节点的值小于max，则产生max-value的水量，否则产生的水量为0
				water += Math.max(0, max - value);
				isEnter[r - 1][c] = true;
				heap.add(new Node(heightMap[r - 1][c], r - 1, c));
			}
			// 如果有下面的位置并且下面的位置没有进过堆
			// 将当前节点下方的没有进过堆的节点入堆，并且在入堆时结算水量
			if (r < N - 1 && !isEnter[r + 1][c]) {
				value = heightMap[r + 1][c];
				water += Math.max(0, max - value);
				isEnter[r + 1][c] = true;
				heap.add(new Node(heightMap[r + 1][c], r + 1, c));

			}
			// 如果有左面的位置并且左面的位置没有进过堆
			// 将当前节点左方的没有进过堆的节点入堆，并且在入堆时结算水量
			if (c > 0 && !isEnter[r][c - 1]) {
				value = heightMap[r][c - 1];
				water += Math.max(0, max - value);
				isEnter[r][c - 1] = true;
				heap.add(new Node(heightMap[r][c - 1], r, c - 1));
			}
			// 如果有右面的位置并且右面的位置没有进过堆
			// 将当前节点右方的没有进过堆的节点入堆，并且在入堆时结算水量
			if (c < M - 1 && !isEnter[r][c + 1]) {
				value = heightMap[r][c + 1];
				water += Math.max(0, max - value);
				isEnter[r][c + 1] = true;
				heap.add(new Node(heightMap[r][c + 1], r, c + 1));
			}
		}
		return water;
	}

}
